/*
 * @lc app=leetcode.cn id=779 lang=javascript
 *
 * [779] 第K个语法符号
 */

// @lc code=start
/**
 * @param {number} N
 * @param {number} K
 * @return {number}
 */
var kthGrammar = function (N, K) {
  // 右子树是左子树的反转
  if (N === 1) return 0;
  // K在父节点左子树上
  if (K <= 1 << (N - 2)) return kthGrammar(N - 1, K);
  // K在父节右子树
  return kthGrammar(N - 1, K - (1 << (N - 2))) ^ 1;
};
// @lc code=end
